#include <stdio.h>
#include <stdlib.h>

// 定义二叉排序树节点结构
typedef struct Node {
    int data;  // 节点值
    struct Node* left;  // 左子节点
    struct Node* right;  // 右子节点
} Node;

// 创建新节点
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode) {
        newNode->data = data;
        newNode->left = NULL;
        newNode->right = NULL;
    }
    return newNode;
}

// 插入新节点到BST
Node* insert(Node* root, int data) {
    if (root == NULL) {  // 如果BST是空的，创建根节点
        return createNode(data);
    }

    if (data < root->data) {
        root->left = insert(root->left, data);  // 插入到左子树
    } else {
        root->right = insert(root->right, data);  // 插入到右子树
    }

    return root;
}

// 在BST中查找节点
Node* search(Node* root, int data) {
    if (root == NULL || root->data == data) {  // 如果节点为空或找到目标
        return root;
    }

    if (data < root->data) {  // 如果目标值小于当前节点，查找左子树
        return search(root->left, data);
    } else {  // 否则查找右子树
        return search(root->right, data);
    }
}

// 前序遍历
void preOrder(Node* root) {
    if (root != NULL) {
        printf("%d ", root->data);
        preOrder(root->left);
        preOrder(root->right);
    }
}

int main() {
    Node* root = NULL;
    root = insert(root, 5);  // 插入节点
    insert(root, 3);
    insert(root, 8);
    insert(root, 1);
    insert(root, 4);

    printf("前序遍历: ");
    preOrder(root);  // 前序遍历树
    printf("\n");

    int target = 4;  // 查找节点
    Node* result = search(root, target);
    if (result != NULL) {
        printf("找到节点: %d\n", result->data);
    } else {
        printf("未找到节点\n");
    }

    return 0;
}
